Distributed networks are continually becoming larger in their coverage area and faster in their message delivery. However, the tendency of distributed systems to cover large areas naturally reduces the speed of message delivery, i.e., increases message latency. Part of this speed reduction is a result of physical limitations, e.g., messages cannot travel faster than the speed of light and therefore message latency inherently increases with distance. However, message latency is further increased due to the overhead of a causally ordered network. Causal ordering is a property that guarantees a certain order of message delivery. If a node receives a first message, it may respond to it by sending out a second message. Any node in a causal ordered network that receives both messages will receive the first message before it receives the second message.
In a causally ordered network, when a node receives a message, before the node can respond to the message it must be certain that it will not receive any other message from any other node that causally proceeds that message. Therefore, the node must utilize some type of ordering scheme to signify when it can respond. One common scheme attaches a marker to a message for indicating the causal ordering of the message. However, this scheme is not desirable due to the bandwidth overhead required by the markers and the difficulty in implementation. Another scheme uses the creation time of the message to impose causal order by attaching time stamps to the message. This scheme works well because the time stamps consume very little bandwidth. However, the use of time-stamps do incur additional message delay. For example, when a node N receives a time-stamped message m, it must wait until it receives a message from every other node in the network with a time stamp equal to or greater than the one of message m. In this way, node N is certain that a causally ordered response to the message m does not depend on another message on its way to the node N but not yet received. Once the node N has received messages from all the remaining nodes with time-stamps greater than or equal to the time-stamp of the message m, causal ordering is thereby assured.
The delay in waiting for messages from the remaining nodes can be extensive. For example, in a network spanning the United States, a delay between the farthest-most nodes, even using optical fibers, is often greater than 25 milliseconds (ms). As a result, the causal response to every message, even those that are received in less than 25 ms, must be delayed for at least 25 ms.
This problem is exacerbated by the discrepancy of clock readings from node to node. Typically each node has either a logical clock or a physical clock. Although logical clocks, such as Lamport clocks, are easy to maintain and do not suffer from significant skew or drift, they do not allow the network to exploit knowledge about minimum message delay used by each node. Furthermore, independent physical clocks, such as a separate clock in each node, experience a significant amount of skew and drift between the different nodes. Even by applying sophisticated synchronization algorithms, the difference in the physical clock readings from node to node often cause a significant increase to message latency.
Therefore, what is needed is a system and method that allows a node to respond as quickly as possible to a received message, while still being assured that the response is causally ordered.